Multiprocessor computer systems comprise a number of processing element nodes connected together by an interconnect network. The interconnect network transmits packets of information between nodes. Packets comprise multiple physical transfer units (phits). A phit is typically the width of a network physical communication link or physical channel between processing element nodes. The interconnect network typically carries normal traffic and maintenance traffic. Examples of information possibly contained in a normal traffic packet are messages, a shared-memory operation, or various forms of data. The maintenance traffic, on the other hand, is used for such tasks as system initialization, system configuration, diagnostics, hardware monitoring, error monitoring, performance monitoring, and other such maintenance tasks.
In previous multiprocessor computer systems, the maintenance traffic travels on its own physical maintenance network, which includes physical communication links not used by the normal communication traffic. In fact, the physical communication links used by the normal traffic are completely separate from the physical maintenance network. In other words, the conventional interconnect network includes one set of wires to carry maintenance traffic and a different set of wires to carry normal traffic.
The normal traffic portion of the interconnect network is typically flow controlled such as with store-and-forward mechanisms where packets are transferred in single units from node to node along the path from source to destination. Each node waits to pass the head of a packet onto the next node until the last phit of the packet has been received. More recent multiprocessor systems utilize normal traffic interconnect networks using some form of wormhole routing to control the flow of normal traffic packets. Wormhole routing interconnect networks route the head of the packet from a node before the tail of the packet is received by that node. The packet is divided into a number of smaller message packets called flow control units (flits), which may be one or more phits. A header flit contains routing information. The header flit is received by a processing element node and examined as to its destination. The header flit is sent on to the next node indicated by the routing algorithm. The remaining flits follow behind the header flit in a train-like fashion. Flow control between nodes is accomplished on a flit-by-flit basis, rather than a packet-by-packet basis as in the store-and-forward interconnect networks. Thus, in wormhole routing, a packet may be partially transmitted across a physical communication link, and then blocked due to a shortage of buffer space in the receiving node.
Worm hole routing significantly reduces packet latency in lightly loaded networks, because the time to transmit the packet onto a link (phits per packet times clock period) is suffered only once per network transversal, rather than once per hop. Wormhole routing also significantly reduces network buffering requirements, as a node is not required to buffer an entire packet.
A problem with wormhole routing, however, is that when a header flit blocks, the remaining flits stall behind the header. These remaining flits may possibly be across multiple links and nodes in the network. A blocked packet may prevent other packets from proceeding, even those that do not want to route through the node at which the header flit is blocked. This can cause significant network degradation, especially in the presence of non-uniform communication patterns.
A third type of normal traffic interconnect network is a virtual cut-through network. A virtual cut-through interconnect network is similar to wormhole routing networks, except that when a packet blocks a buffer, that buffer must always accept the entire packet. Thus, virtual cut-through routing avoids some problems inherent in the blocking occurring in wormhole routing, but at the cost of additional hardware necessary to buffer all of the blocked packets.
Deadlock occurs when cyclic dependencies arise among a set of channel buffers, causing all involved buffers to fill up and block. A primary consideration in the design of interconnect networks and corresponding routing algorithms is avoiding deadlock. Deadlock situations can be formalized via a channel dependency graph, a directed graph whose nodes represent network channels and whose arcs represent dependencies between channels. An arc exists between channels x and y if a packet can route directly from channel x to channel y. It can be proven that a network is deadlock free if its channel dependency graph is acyclic. However, even if a healthy network can be proven to be deadlock free, deadlock could still occur due to a fault in the network.
One simple method to avoid deadlock is to restrict the topology of the interconnect network and/or the routing function used to route packets between the processing element nodes on the interconnect network to remove the possibility of cyclic buffer dependencies. For example, a binary hypercube topology is deadlock-free if the routing function is restricted so that the dimensions are always traversed in increasing order using the e-cube or dimension order routing algorithm. Since at most one hop is made per dimension and no packets route to a lower dimension, there can be no cyclic buffer dependencies. The e-cube routing algorithm can also be used to make an n-dimensional mesh topology deadlock-free, since the opposite-flowing traffic in each dimension uses distinct sets of buffers and the dimensions are traversed in increasing order. The torus topology, however, is not deadlock free when restricted to e-cube routing, because the wrap-around links in the torus topology allow cyclic buffer dependencies to form on a single ring.
In addition, even in meshes, deadlock can arise due to dependencies between request and response packets. Since a node may not be able to accept more request packets until that node has transmitted response packets for previous requests, deadlock can occur if response packets are made to wait behind request packets in the network. An expensive solution to this dependency problem between request and response packets is to use separate physical networks for requests and responses.
Virtual channels have been used to avoid deadlock and to reduce network congestion for normal traffic. Each physical channel is broken up into one or more virtual channels. Each virtual channel includes virtual channel buffers to store packets along a virtual path. The virtual channels are multiplexed across common physical channels, but otherwise operate independently. Thus, a blocked packet on a first virtual channel multiplexed across the common physical channel does not block packets behind a second virtual channel multiplexed on the common physical channel.